from typing import Optional
from collections import defaultdict

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def __str__(self):
        return str(self.val)

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        profits_white = defaultdict(int)
        profits_black = defaultdict(int)

        def visit(node: TreeNode):
            if node.left:
                visit(node.left)
            if node.right:
                visit(node.right)

            profits_white[node] = 0
            if node.left:
                profits_white[node] += max(profits_white[node.left], profits_black[node.left])
            if node.right:
                profits_white[node] += max(profits_white[node.right], profits_black[node.right])

            profits_black[node] = node.val
            if node.left:
                profits_black[node] += profits_white[node.left]
            if node.right:
                profits_black[node] += profits_white[node.right]
        visit(root)

        #######
        def display(node: TreeNode):
            if node is None:
                return

            print(node.val, profits_white[node], profits_black[node], sep=',', end=' ')
            display(node.left)
            display(node.right)
        display(root)
        print()
        #######
        return max(profits_white[root], profits_black[root])


values = [3,2,3,None,3,None,1]
def values2tree(values):
    nodes = [TreeNode(v) if v is not None else None for v in values]
    for i in range(len(nodes)):
        if 2 * i + 1 < len(nodes):
            nodes[i].left = nodes[2 * i + 1]
        if 2 * i + 2 < len(nodes):
            nodes[i].right = nodes[2 * i + 2]
    return nodes[0]
res = Solution().rob(values2tree(values))
print(res)




